package com.fwpsl.graph.shortestpath.singlesource;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

import static com.fwpsl.graph.shortestpath.singlesource.AbstractSingleSource.PathNode.PATH_NODE_TYPE_MULTI;
import static com.fwpsl.graph.shortestpath.singlesource.AbstractSingleSource.PathNode.PATH_NODE_TYPE_SINGLE;

/**
 * @author: 风戏fw
 * @date: 2024/4/1
 * @description: Dijkstra(迪杰斯特拉)算法用于在带权重的图中找到从源节点到所有其他节点的最短路径。
 * 应用场景：Dijkstra算法常用于地图应用中的路线规划、网络路由选择、物流配送等场景，用于找出从一个固定起点到其他所有点的最短路径。
 * 注意事项：
 * 1. Dijkstra算法不能处理带有负权边的图，因为负权边可能导致算法无法正确计算出最短路径。
 * 2. 在实际应用中，可以使用优先队列（如最小堆）来优化选择未处理顶点的步骤，这样可以减少查找最小距离顶点的时间复杂度。
 * 3. Dijkstra算法可以很容易地扩展到处理稀疏图，因为只需要处理与当前顶点直接相连的边。
 */
public class Dijkstra<T> extends AbstractSingleSource<T> {

    /**
     * 最短路径（单条）
     */
    @Override
    public Map<Vertex<T>, PathNode> singlePathList(Graph<T> graph, Vertex<T> start) {
        // 图中所有顶点
        List<Vertex<T>> vertices = graph.getVertices();

        // 集合S：存放从起点到各个顶点的最短路径
        // 距离数组dist[]：用于存放从起点到各个顶点的最短距离估计值，初始时起点的距离为0，其它顶点为INF
        Map<Vertex<T>, PathNode> distances = new HashMap<>();
        for (Vertex<T> v : vertices) {
            distances.put(v, new PathNode(v, INF, PATH_NODE_TYPE_SINGLE));
        }
        distances.get(start).distance = 0;

        // 优先队列， 优先处理最短路径的顶点
        PriorityQueue<PathNode> pq = new PriorityQueue<>(Comparator.comparingInt(v -> v.distance));
        pq.offer(distances.get(start));
        while (!pq.isEmpty()) {
            PathNode currentNode = pq.poll();
            Vertex<T> currentVertex = currentNode.currentVertex;

            // 遍历与顶点u相连的所有边(u, v)，更新起点到顶点v的最短距离估计值：
            // 如果通过u到达v的距离（即dist[u] + weight(u, v)）小于当前dist[v]的值，则更新dist[v]为较小的值。
            for (Edge<T> edge : currentVertex.getEdges()) {
                int tempDistance = (int) (currentNode.distance + edge.getWeight());
                if (tempDistance < distances.get(edge.getDestination()).distance) {
                    PathNode pathNode = distances.get(edge.getDestination());
                    pathNode.preVertex = currentVertex;
                    pathNode.distance = tempDistance;
                    pq.offer(pathNode);
                }
            }
        }
        return distances;
    }

    /**
     * 最短路径（多条）
     */
    @Override
    public Map<Vertex<T>, PathNode> multiPathList(Graph<T> graph, Vertex<T> start) {
        List<Vertex<T>> vertices = graph.getVertices();

        Map<Vertex<T>, PathNode> distances = new HashMap<>();
        for (Vertex<T> v : vertices) {
            distances.put(v, new PathNode(v, INF, PATH_NODE_TYPE_MULTI));
        }
        distances.get(start).distance = 0;
        distances.get(start).preVertexSet = new HashSet<>();

        PriorityQueue<PathNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
        pq.offer(distances.get(start));
        while (!pq.isEmpty()) {
            PathNode currentNode = pq.poll();
            Vertex<T> currentVertex = currentNode.currentVertex;

            for (Edge<T> edge : currentVertex.getEdges()) {
                int tempDistance = (int) (currentNode.distance + edge.getWeight());
                if (tempDistance < distances.get(edge.getDestination()).distance) {
                    PathNode pathNode = distances.get(edge.getDestination());
                    pathNode.distance = tempDistance;
                    pathNode.preVertexSet = new HashSet<>();
                    pathNode.preVertexSet.add(currentVertex);
                    pq.offer(pathNode);
                } else if (tempDistance == distances.get(edge.getDestination()).distance) {
                    distances.get(edge.getDestination()).preVertexSet.add(currentVertex);
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        int[][] graphEdgeArr = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        Graph<Integer> graph = Graph.buildIntGraph(graphEdgeArr);
        Integer start = 1, end = 5;

        Dijkstra<Integer> dijkstra = new Dijkstra<>();
        // 单条最短路径
        dijkstra.testSinglePathList(graph, start, end);

        System.out.println();

        // 多条最短路径
        dijkstra.testMultiPathList(graph, start, end);
    }
}
